\chapter{Dobrá předuspořádání}

V této kapitole se zaměříme na pojem \emph{dobré předuspořádání}. 
Nejprve zadefinujeme potřebné pojmy a následně si ukážeme, jak lze u předuspořádání zjistit, jestli je dobré.




\begin{definice}
\label{wqod}
\emph{Dobré předuspořádání} na množině $S$ je reflexivní a tranzitivní relace (předuspořádání),
pro kterou platí, že každá neprázdná podmnožina $X\subseteq S$ obsahuje alespoň jeden minimální prvek a nejvýše 
konečně mnoho takových, které po dvou nejsou vzájemně ekvivalentní (nejsou v relaci $\sim$ viz jádro předuspořádání). 
\end{definice}

Jde o zobecnění pojmu \emph{dobrého uspořádání} 
a tento popis se definici dobrého uspořádání nejvíce blíží. Existuje však více zbůsobů jak definovat dobré předuspořádání, z nichž několik uvedeme
 v následující větě. 
 
\begin{veta} 
\label{wqo}
 Pro předuspořádání $\leq$ na množině $S$ jsou následující podmínky ekvivalentní:

\begin{enumerate}
  \item[(i)] $\leq$ je dobré předuspořádání.
  \item[(ii)] Každá podmnožina $X \subseteq  S$ obsahuje konečnou podmnožinu $Y\subseteq X$ takovou, 
  že
  \[ \forall x \in X \  \exists y \in Y : y \le x.\]

  \item[(iii)] V libovolné posloupnosti $\{ x_i \}_{i=1}^\infty $ existují $i,j \in \mathbb{N}, i < j$ taková,
   že platí $x_i \leq x_j.$ 
  \item[(iv)] Libovolná nekonečná posloupnost prvků z $S$ obsahuje nekonečnou rostoucí podposloupnost.
  \item[(v)] Množina $S$ neobsahuje ostře klesající nekonečnou posloupnost ani nekonečnou posloupnost vzájemně neporovnatelných prvků.
  \item[(vi)] Libovolná posloupnost uzavřených podmnožin $S$, která je ostře rostoucí vzhledem k inkluzi, je konečná.
\end{enumerate}
\end{veta}

\begin{proof}

(i)$\Longrightarrow$(ii)
Nechť $X\subseteq S, X\not =\O$ je libovolná. Pak podle definice \label{wqod} je množina minimálních prvků množiny $X$ neprázdná, nazvěme ji $Y$. Dále podle definice je jádro množiny $Y$ konečné, můžeme tedy z každé třídy ekvivalence vzít jeden prvek a dostaneme konečnou množinu $\bar{Y}$. Potom  $\bar{Y}$ musí splňovat podmínku (ii) pro množinu $X$. V opačném případě by existoval prvek $x \in X$ takový, že množina $\{z\in X, z \leq x\}$ nemá minimální prvek, což je spor s (i).

(ii)$\Longrightarrow$(iv)
Nechť  $\{ x_i \}_{i=1}^\infty $ je libovolná posloupnost prvků  z $S$. Dále $X=\{x_1, x_2, \ldots\}$ a $Y=\{x_{l_1}, x_{l_2}, \ldots, x_{l_n}\}$ buď konečná množina minimálních prvků z $X$ podle (ii). Alespoň jedna z množin $Y_i=\{x_j\in X, x_{l_i}\leq x_j \wedge j>l_i\}, i\in\{1, ..., n\}$ je nutně nekonečná, například $Y_k$. Prvek $x_{l_k}$ bude prvním prvkem rostoucí podposloupnosti, dále budeme pokračovat s množinou $Y_{k}\minus \{x_{l_k}\}$.

(iv)$\Longrightarrow$(v)
Zřejmé.



(v)$\Longrightarrow$(iii)
Nechť $\{ x_i \}_{i=1}^\infty $ je libovolná posloupnost prvků množiny $S$. Podle (v) nemůžou být všechny prvky vzájemně neporovnatelné. Dále pokud by pro každou dvojici porovnatelných prvků platilo $x_i<x_j \Longrightarrow i>j$, byl by to spor s tím, že posloupnost $\{ x_i \}_{i=1}^\infty $ nemůže obsahovat ostře klesající podposloupnost. 

(iii)$\Longrightarrow$(vi)
Předpokládejme, že platí (iii) a neplatí (vi). Existuje tedy nekonečná posloupnost $(X_i)_{i=1}^{\infty}$ podmnožin množiny $X$, které jsou uzavřené vzhledem k $\leq$ a pro které platí 
\[X_1 \subset X_2 \subset \cdots \subset X_n \subset \cdots.\]
Potom pro každé $i \geq 2$ existuje prvek $x_i \in X_i \setminus X_{i-1}$. Posloupnost  $(x_i)_{i=2}^\infty$ nesplňuje podmínku (iii), v opačném případě by totiž z $x_i\leq x_j, i<j$ a uzavřenosti množiny $X_i$ plynulo $x_j \in X_i$, což je spor.
 
(vi)$\Longrightarrow$(i)
Nejprve ukážeme, že libovolná podmnožina $X\subseteq S$ má minimální prvek. Pokud by platil opak, obsahovala by množina $X$ nekonečnou ostře klesající posloupnost $(x_i)_{i=1}^\infty$. Nechť množina $ X_i$ je uzávěr množiny $\{x_i\}$. Pak posloupnost $(X_i)_{i=1}^{\infty}$ je ve sporu s (vi). 

Dále předpokládejme, že podmnožina $Y$ minimálních prvků množiny $X$ má nekonečné jádro. Nechť $(y_i)_{i=1}^\infty$ je posloupnost prvků množiny $Y$, kde každý prvek je z jiné třídy jádra. Pak posloupnost 
\[\{y_1\}\subset \{y_1, y_2\}\subset \cdots \subset \{y_1, y_2, ..., y_n\} \subset \cdots\]
je ve sporu s podmínkou (vi).
\end{proof}

\begin{pozn}
Všimněme si, že  v důkazech (iii)$\Longrightarrow$(vi) a (vi)$\Longrightarrow$(i) jsme použili axiom výběru. Ekvivalence některých podmínek na něm proto asi závisí.
\end{pozn}


Druhá z podmínek se nazývá \emph{vlastnost konečné báze}. Každá uzavřená množina $X$ totiž obsahuje konečnou podmnožinu, jejímž uzávěrem je 
právě množina $X$, která je tak konečně generovaná.Při rozpoznávání jazyků monotónními předuspořádáními nám k regularitě místo konečného indexu stačí vlastnost konečné báze, jak vyplyne z důkazu zobecněné Myhilovy-Nerodovy věty.



Užitečným nástrojem pro dokázání, že dané předuspořádání je dobré, poskytuje věta, kterou poprvé dokázal Nash-Williams. K jejímu formulování potřebujeme definovat několik pojmů.

\begin{definice}
Nechť $X$ je množina s předuspořádáním $\leq$ a $(x_i)_{i=1}^\infty$ je nekonečná posloupnost prvků množiny $X$. Posloupnost   $(x_i)_{i=1}^\infty$ nazveme \emph{špatnou}, právě když platí
\[  \forall i,j \in \mathbb{N} : i < j  \Longrightarrow x_i \not \leq x_j.\]
\end{definice}

Název \emph{špatná posloupnost} odpovídá tomu, že jsou to práve tyto po\-sloup\-nos\-ti, které nesmí obsahovat dobře před\-uspořá\-da\-ná množina.

\begin{definice}
Nechť $\leq$ je předuspořádání na množině $X$. Potom předuspořádání $\leq$ nazveme \emph{fundované}, právě když neexistuje nekonečná ostře klesající posloupnost prvků množiny $X$..
\end{definice}

Uveďme, že každé dobré předuspořádání je fundované, jak vyplývá z definice \ref{wqo}(iv). 

\begin{veta} 
\label{fund}
Předuspořádání  $\leq$ na množině $X$ je fundované, právě když každá neprázdná podmnožina $A\subseteq X$ obsahuje minimální prvek.
\end{veta}

\begin{proof}

$"\Longleftarrow"$ Dokážeme obměněnou implikaci. Pokud tedy není $\leq$ fundované, existuje nekonečná ostře klesající posloupnost $(x_i)_{i=1}^\infty, x_i \in X$. Potom množina $X_0=\{x_i| i\geq 1\}$ zřejmě neobsahuje minimální prvek.

$"\Longrightarrow"$ Nechť $A\subseteq X$ je libovolná neprázdná podmnožina a $x_0 \in A$ je libovolný prvek. Potom je $x_0$ buď minimální, nebo existuje $x_1 \in A$, $x_1 < x_0$. Opakováním tohoto argumentu musíme po konečném počtu kroků nalézt $i \in \mathbb{N}$ takové, že $x_i$ je minimální. V opačném případě bychom dostali nekonečnou ostře klesající posloupnost, což podle předpokladu není možné. 
\end{proof}

Pro potřeby následující věty je nutné definovat lexikografické předuspořádání na nekonečných posloupnostech. Nechť $X$ je množina předuspořádaná relací $\leq$ a $\sim$ je její jádro. Definujme množinu nekonečných posloupností jako $X^{\omega}$. Potom předuspořádání $\leq$ indukuje předuspořádání na množině $X^{\omega}$ následujícím vztahem:
\[ (x_i)_{i=1}^\infty \leq  (y_i)_{i=1}^\infty \Longleftrightarrow \forall i \in \mathbb{N} : x_i \sim y_i \text{ nebo}\]
\[ \exists n\geq 1 : x_n < y_n \wedge \forall i<n : x_i \sim y_i     .\]

Důkaz následující věty je převzat z \cite{4}.
\begin{veta}

Nechť $\preceq$ je fundované předuspořádání na množině $X$. Nechť dále $\leq$ je předuspořádání na množině $X$, které není dobré. Potom existuje špatná posloupnost $(x_i)_{i=1}^\infty \in X^{\omega}$ vzhledem k předuspořádání $\leq$, která je minimální vzhledem k $\preceq$.

\end{veta}

\begin{proof}
Aby předuspořádání $\leq$ nebylo dobré, musí podle věty \ref{wqo}(iii) existovat alespoň jedna špatná posloupnost prvků množiny $X$. Množinu všech takovývh posloupností nazvěme $B_0$. Budeme induktivně vytvářet posloupnost $x \in X^{\omega}$. Množina $\{y_0| y\in B_0\}$ má podle \ref{fund} minimální prvek vzhledem k $\preceq$, vyberme jeden a nazvěme jej $x_0$. Pro každé $i\geq 0$ dále definujeme $B_{i+1}=\{y\in B_i| y_i = x_i\}$ a opakujeme předchozí krok pro $i+1$. Musíme ověřit, že takto sestrojená posloupnost je špatna. Pokud by tomu tak nebylo, existovala by $i, j \geq 0, i<j$ taková, že $x_i \leq x_j$. To je ovšem spor s tím, že $x_0, x_1, \ldots, x_j$ je prvních $j+1$ členů nějaké posloupnosti z $B_0$, která je špatná. Tímto postupem jsme dostali minimální špatnou posloupnost $x\in X^{\omega}$ vzhledem k $\leq$, která je minimální vzhledem k $\preceq$, což jsme chtěli dokázat. 
\end{proof}


\cleardoublepage

